package com.finance.system.test;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 图的深度优先算法和广度优先算法
 */
public class DBFs {
    @Data
    static class ArcNode{
        int val;
        ArcNode next;
    }
    @Data
    static class VNode{
        int val;
        ArcNode firstArc;

        public void offer( ArcNode node){
            if(this.firstArc == null){
                this.firstArc = node;
            }else{
                ArcNode tempNode = firstArc;
                while(tempNode.next != null){
                    tempNode = tempNode.next;
                }
                tempNode.next = node;
            }
        }
    }

    public static void main(String[] args) {
        int[][] arcNodeArr = {{0,1,3,4},{1,0,2,3},{2,1,3,4},{3,0,1,2,4},{4,0,2,3}};
        VNode[] arcList = new VNode[arcNodeArr.length];
        for (int i = 0; i < arcNodeArr.length; i++) {
            VNode vNode = new VNode();
            vNode.val = i;
            arcList[i] = vNode;
            for (int j = 1; j < arcNodeArr[i].length; j++) {
                ArcNode arcNode1 = new ArcNode();
                arcNode1.val = arcNodeArr[i][j];
                vNode.offer(arcNode1);
            }
        }

        int[] visitedList = new int[arcList.length];
        for (int i = 0; i < arcList.length; i++) {
            visitedList[i] = 0;
        }
        List<Integer> numberList = new ArrayList<>();
        List<Integer> pathList = new ArrayList<>();
        Queue<Integer> queue = new ArrayBlockingQueue<Integer>(5);
       /* System.out.println("dfs 遍历");
        searchDfs(arcList[4],arcList,visitedList,numberList);
        for (int i = 0; i < arcList.length; i++) {
            visitedList[i] = 0;
        }
        numberList.clear();
        System.out.println();

        findDfs(arcList[1],arcList,visitedList,4,numberList,pathList);
        System.out.println(pathList);*/

        /*System.out.println("bfs 遍历");
        searchBfs(arcList[4],arcList,visitedList,numberList,queue);
        System.out.println();*/

        findBfs(arcList[1],arcList,visitedList,4,numberList,pathList,queue);
        System.out.println(pathList);


    }

    public static void searchDfs(VNode vNode, VNode[] arcList, int[] visitedList, List<Integer> numberList){
        int val = vNode.val;
        visitedList[val]=1;numberList.add(1);
        System.out.print(val + " ");
        ArcNode tempArc = vNode.firstArc;
        while(tempArc != null && numberList.size() < arcList.length){
            int arcVal = tempArc.val;
            if(visitedList[arcVal] == 0){
                searchDfs(arcList[arcVal],arcList,visitedList,numberList);
            }
            tempArc = tempArc.next;
        }

    }


    public static void searchBfs(VNode vNode, VNode[] arcList, int[] visitedList,
                                 List<Integer> numberList, Queue<Integer> queue){
        int val = vNode.val;
        if(visitedList[val] == 0){
            visitedList[val]=1;numberList.add(1);
            System.out.print(val + " ");
        }
        //1、从第一个元素开始
        ArcNode firstArc = vNode.firstArc;
        ArcNode tempArc = firstArc;
        // 当访问元素不超过总元素个数可继续查找
        while(numberList.size() < arcList.length){
            int arcVal = tempArc.val;
            //判断元素是否已访问过
            if(visitedList[arcVal] == 0){
                //先访问元素 输出、更新访问标记、访问元素数量+1
                System.out.print(arcVal + " ");
                visitedList[arcVal]=1;numberList.add(1);

                //将访问过的元素放进队列
                queue.offer(arcVal);

            }
            if(tempArc.next != null){
                tempArc = tempArc.next;
            }else{
                Integer peek = queue.peek();
                if(peek != null){
                    searchBfs(arcList[peek],arcList,visitedList,numberList,queue);
                }
            }
        }

    }

    /**
     * 查找节点到k的一条路径
     * @param vNode
     * @param arcList
     * @param visitedList
     * @param k
     * @param path
     */
    public static void findDfs(VNode vNode, VNode[] arcList, int[] visitedList,int k,
                               List<Integer> numberList,
                               List<Integer> path){
        int val = vNode.val;

        //先访问元素 加入path中、更新访问标记、访问元素数量+1
        path.add(val);
        visitedList[val] = 1;
        numberList.add(1);

        if(val == k) {
            path.add(val);
            return;
        }
        //1、从第一个元素开始
        ArcNode firstArc = vNode.firstArc;
        ArcNode tempNode = firstArc;
        // 当访问元素不超过总元素个数 且下一个元素不为空 可继续查找
        while(tempNode != null && numberList.size() < arcList.length){
            int tempVal = tempNode.val;
            //判断元素是否已访问过
            if(visitedList[tempVal] == 0){
                findDfs(arcList[tempVal],arcList,visitedList,k,numberList,path);
            }else {
                if(tempNode.next != null){
                    tempNode = tempNode.next;
                }
            }

        }
    }

    /**
     * 利用广度优先算法寻找v到k的一条简单路径
     * @param vNode
     * @param arcList
     * @param visitedList
     * @param k
     * @param numberList
     * @param path
     * @param queue
     */
    public static void findBfs(VNode vNode, VNode[] arcList, int[] visitedList,int k,
                               List<Integer> numberList,
                               List<Integer> path,Queue<Integer> queue){
        int val = vNode.val;

        //先访问元素 加入path中、更新访问标记、访问元素数量+1
        if(visitedList[val] == 0){
            path.add(val);
            visitedList[val] = 1;
            numberList.add(1);
        }

        if(val == k) {
            path.add(val);
            return;
        }
        //1、从第一个元素开始
        ArcNode firstArc = vNode.firstArc;
        ArcNode tempNode = firstArc;
        // 当访问元素不超过总元素个数 且下一个元素不为空 可继续查找
        while(numberList.size() < arcList.length){
            int tempVal = tempNode.val;
            //判断元素是否已访问过
            if(visitedList[tempVal] == 0){
                //去访问，并将此节点放进队列
                path.add(tempVal);
                visitedList[tempVal] = 1;
                numberList.add(1);
                queue.offer(tempVal);
            }
            if(tempNode.next != null){
                tempNode = tempNode.next;
            }else{
                Integer peek = queue.peek();
                if(peek != null){
                    findBfs(arcList[peek],arcList,visitedList,k,numberList,path,queue);
                }
            }

        }
    }
}
